package 栈;
import java.util.*;

/**
 * 该类用于计算直方图中最大的矩形面积。
 * 时间复杂度：O(n)，空间复杂度：O(n)
 */
public class largestRectangleArea {
    /**
     * 计算直方图中最大的矩形面积。
     * 该方法使用单调栈来维护递增的高度，通过计算每个高度对应的宽度来找到最大面积。
     * @param heights 表示每个位置的高度数组
     * @return 最大的矩形面积
     */
    public int largeRecArea(int[] heights){
        ArrayDeque<Integer> stack = new ArrayDeque<>(); // 创建一个栈来存储索引
        stack.push(-1); // 初始化栈，-1 表示边界
        int max = 0; // 初始化最大面积
        for(int i = 0; i < heights.length; i++){
            // 当栈顶元素的高度大于等于当前高度时，计算以栈顶为高的最大矩形面积
            while(stack.peek() != -1 && heights[i] <= heights[stack.peek()]){
                int h = heights[stack.pop()]; // 弹出栈顶元素的高度
                // 遍历每个高度，是要以当前高度为基准，寻找最大的宽度 
                // 组成最大的矩形面积那就是要找左边第一个小于当前高度的下标left，
                // 再找右边第一个小于当前高度的下标right，那宽度就是这两个下标之间的距离了 
                // 但是要排除这两个下标，所以是right-left-1，用单调栈就可以很方便确定这两个边界
                int w = i - stack.peek() - 1; // 计算宽度
                max = Math.max(max, w * h); // 更新最大面积
            }
            stack.push(i); // 将当前索引入栈
        }
        // 处理栈中剩余的元素
        while(stack.peek() != -1){
            int h = heights[stack.pop()]; // 弹出栈顶元素的高度
            int w = heights.length - stack.peek() - 1; // 计算宽度
            max = Math.max(max, w * h); // 更新最大面积
        }
        return max; // 返回最大面积
    }

    /**
     * 主方法，处理输入并输出结果。
     * 该方法从标准输入读取高度数组，并输出最大的矩形面积。
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建扫描器对象
        String[] s = sc.nextLine().split(","); // 读取高度数组
        int[] heights = new int[s.length]; // 创建高度数组
        for(int i = 0; i < s.length; i++){
            heights[i] = Integer.parseInt(s[i]); // 解析高度数组
        }
        largestRectangleArea ma = new largestRectangleArea(); // 创建对象
        System.out.println(ma.largeRecArea(heights)); // 输出最大的矩形面积
        sc.close(); // 关闭扫描器
    }
}
